/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class RangeSumQueryMutable {
	class Node {
		int left;
		int right;
		Node leftChild;
		Node rightChild;
		int sum;

		public Node(int i, int val) {
			this.left = i;
			this.right = val;
		}
	}

	int[] a;
	Node root;

	/**
	 * 新建
	 * 
	 * @param nums
	 */
	public RangeSumQueryMutable(int[] nums) {
		a = nums;
		root = BuildTree(0, a.length - 1, nums);
	}

	private Node BuildTree(int i, int j, int[] nums) {
		if (i > j) {
			return null;
		}
		if (i == j) {
			Node cur = new Node(i, i);
			cur.sum = nums[i];
			return cur;
		}
		Node cur = new Node(i, j);
		int mid = i + (j - i) / 2;
		cur.leftChild = BuildTree(i, mid, nums);
		cur.rightChild = BuildTree(mid + 1, j, nums);
		cur.sum = cur.leftChild.sum + cur.rightChild.sum;
		return cur;
	}

	public int sumRange(int i, int j) {
		return getRes(root, i, j);
	}

	private int getRes(Node root, int i, int j) {
		if (root.left == i && root.right == j) {// 覆盖
			return root.sum;
		}
		int mid = root.left + (root.right - root.left) / 2;
		if (mid >= j) {
			return getRes(root.leftChild, i, j);
		}
		if (mid < i) {
			return getRes(root.rightChild, i, j);
		}
		return getRes(root.leftChild, i, mid) + getRes(root.rightChild, mid + 1, j);
	}

	public void update(int i, int val) {
		Node cur = root;
		long diff = val - a[i];
		while (cur.left != cur.right) {
			cur.sum += diff;
			if (i <= cur.leftChild.right) {// 目标在左子树
				cur = cur.leftChild;
			} else {
				cur = cur.rightChild;
			}
		}
		cur.sum += diff;// 目标叶节点
		a[i] += diff;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int a[] = { 7, 2, 7, 2, 0 };
		// ["NumArray","update","update","update","sumRange","update","sumRange",
		// "update","sumRange","sumRange","update"]
		// [[[7,2,7,2,0]],[4,6],[0,2],[0,9],[4,4],[3,8],[0,4],
		// [4,1],[0,3],[0,4],[0,4]]
		// RangeSumQueryMutable rangeSumQueryMutable = new
		// RangeSumQueryMutable(a);
		// rangeSumQueryMutable.update(4, 6);
		// rangeSumQueryMutable.update(0, 2);
		// rangeSumQueryMutable.update(0, 9);
		// System.out.println(rangeSumQueryMutable.sumRange(4, 4));// 正确
		//
		// rangeSumQueryMutable.update(3, 8);
		// System.out.println(rangeSumQueryMutable.sumRange(0, 4));
		//
		// rangeSumQueryMutable.update(4, 1);
		// System.out.println(rangeSumQueryMutable.sumRange(0, 3));
		// System.out.println(rangeSumQueryMutable.sumRange(0, 4));

		int k = 3;
		int[] b = new int[k];
		System.arraycopy(a, 0, b, 0, k);
		for (int i : b) {
			System.out.println(i);
		}
	}

}
